/*
 * @Author: 缄默
 * @Date: 2021-10-26 17:08:00
 * @LastEditors: 缄默
 * @LastEditTime: 2021-10-27 15:31:03
 */

//复制含有随机指针节点的链表

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct ListNode {
    int value;
    ListNode* next;
    ListNode* rand;
    //链表的构造函数
    ListNode(int x) : value(x), next(nullptr), rand(nullptr) { }
    ListNode() : value(0), next(nullptr), rand(nullptr) { }
};

//通过数组生成链表
void foundList(vector<int>& arr, ListNode* const head);

//打印链表
void printList(const ListNode* const head);

//复制链表空间复杂度o（n）
void copyList(ListNode* head);

//不用其他数据形式 有限个额外空间
void betterCopyListNode(ListNode* const head);

int main() {

    vector<int> arr({1,2,3,4,5});
    ListNode* head = new ListNode();
    foundList(arr, head);
    copyList(head);
    cout << endl;
    betterCopyListNode(head);
    return 0;
}

//复杂度为o(n) 空间复杂度为o（n）
void copyList(ListNode* head) {
    ListNode* cur = head;
    map<ListNode*, ListNode*> hashMap;
    while (cur != nullptr) {
        hashMap[cur] = new ListNode(cur->value);
        cur = cur->next;
    }
    cur = head;
    while(cur != nullptr) {
        hashMap[cur]->next = hashMap[cur->next];
        hashMap[cur]->rand = hashMap[cur->rand];
        cur = cur->next;
    }
    printList(hashMap[head]);
    cout << hashMap[head] << "  " << head << endl; 

    return;
}

//打印链表
void printList(const ListNode* const head) {
    ListNode* cur = const_cast<ListNode*>(head);
    while (cur != nullptr) {
        cout << cur->value <<"  " << cur->rand->value << endl;
        cur = cur->next;
    }
    return;
}


void foundList(vector<int>& arr, ListNode* const head) {
    if (arr.size() == 0) return;
    ListNode* cur = head;
    cur->value = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    cur = head;
    ListNode* temp = head;
    for (int i = 0; i < arr.size(); i++) {
        for (int j =0; j < rand() % arr.size(); j++) {
            temp = temp->next;
        }
        cur->rand = temp;
        cur = cur->next;
        temp = head;
    }
    return;
}


void betterCopyListNode(ListNode* const head) {
    ListNode* cur = head;
    //复制节点 并把节点插入到链表中
    while (cur != nullptr) {
        ListNode* copy = new ListNode(cur->value);
        copy->next = cur->next;
        cur->next = copy;
        cur = cur->next->next;
    }

    //将复制后的节点的rand指针设置为对应的值
    cur = head;
    while (cur != nullptr) {
        cur->next->rand = cur->rand->next;
        cur = cur->next->next;
    }
    //删除原来的指针，只留下复制后的
    cur = head->next;
    while (cur != nullptr) {
        if (cur->next != nullptr) {
            cur->next = cur->next->next;
        }
        cur = cur->next;
    }
    printList(head->next);
    return;
}

